package main

import "fmt"

// 如何找出数组中第 k 小的数

func main() {
	arr := []int{6, 1, 7, 2, 5, 3, 8, 4}
	a := findSmallK(arr, 0, len(arr)-1, 3)
	fmt.Println(a)
}

func findSmallK(arr []int, low, high, k int) int {
	fmt.Println("findSmallK")
	fmt.Println("arr = ", arr)
	fmt.Println("low = ", low, " high = ", high, " k = ", k)
	i := low
	j := high
	splitElem := arr[i]

	// 把小于等于 splitElem 的数放到数组中 splitElem 的左边，
	// 大于 splitElem 的值放到右边
	for i < j {
		for i < j && arr[j] >= splitElem {
			j--
		}
		if i < j {
			arr[i] = arr[j]
			fmt.Println("arr = ", arr)
			i++
		}
		for i < j && arr[i] <= splitElem {
			i++
		}
		if i < j {
			arr[j] = arr[i]
			fmt.Println("arr = ", arr)
			j--
		}
	}

	arr[i] = splitElem

	// splitElem 在子数组 arr[low~high] 中下标的偏移量
	subArrayIndex := i - low
	fmt.Println(subArrayIndex)

	if subArrayIndex == k-1 {
		return arr[i]
	} else if subArrayIndex > k-1 {
		return findSmallK(arr, low, i-1, k)
	} else {
		return findSmallK(arr, i+1, high, k-(i-low)-1)
	}
}
